package leetcode.t1Array;


/**
 * 31. 下一个排列
 * 局部交换、排序
 * @author K
 * @date 2024/1/17 13:41
 */
public class T32_NextPermutation {

    public static void nextPermutation(int[] nums) {
        //1. 从后往前找第一个降序num[i]，完了再从后往前第一个大于num[i]的num[j]，交换
        //2. i+1后面的数按升序排列，因为之前都是降序，升序排列只需要前后交换
        int i = nums.length-2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length-1;
            while (j >= 0) {
                if (nums[j] > nums[i]) {
                    swap(nums, i, j);
                    break;
                }
                j--;
            }
        }
        reverse(nums, i +1);
    }

    private static void reverse(int[] nums, int start) {
        int left = start, right = nums.length-1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }


    public static void main(String[] args) {
        int[] nums = {1, 1, 5};
        nextPermutation(nums);
        int[] nums1 = {4,5,2,6,3,1};
        nextPermutation(nums1);
        int[] nums2 = {6,5,4,3,2,1};
        nextPermutation(nums2);
        System.out.println();
    }

}
